package com.wtgroup.demo.leetcode.org_bytedance;

import com.wtgroup.demo.common.bean.LinkNode;

/**
 * 160. 相交链表 https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
 *
 * @author 60906
 * @date 2021/5/6 10:43
 */
public class Q_相交链表 {

    /**
     * [答案]
     * 最一般情况, 一长一短, 短的指针q, 必先到null, 到了null, 会换到长的头.
     * 继续, 当长的指针p到null了, 会换到短上, 此时此刻, 长短的指针p,q恰好对齐.
     */
    private class Solution_LC {

        public LinkNode getIntersectionNode(LinkNode headA, LinkNode headB) {
            if (headA==null || headB==null) {
                return null;
            }

            LinkNode pa = headA;
            LinkNode pb = headB;
            // 只要不相遇, 你们跑到死吧
            while (pa != pb) {
                if (pa == null) {
                    pa = headB;
                } else {
                    pa = pa.next;
                }
                if (pb == null) {
                    pb = headA;
                } else {
                    pb = pb.next;
                }
            }

            return pa;
        }

    }

    /**
     * 本质就是 LC 的"方法三：双指针法",
     * 但LC的指针只用了两个, A的到尾子了, 换到B的头, 同样, B的到尾了, 换到A的头. 巧妙!
     * 注意: A的换到了B, 以后就一直在B上了, 不能再回到A了.
     * 指针复用, 关键是代码简洁了.
     */
    private class Solution {
        public LinkNode getIntersectionNode(LinkNode headA, LinkNode headB) {
            if (headA==null || headB==null) {
                return null;
            }

            LinkNode pa = headA;
            LinkNode pb = headB;
            while (pa!=null && pb!=null) {
                if (pa==pb) {
                    return pa;
                }
                pa = pa.next;
                pb = pb.next;
            }
            LinkNode pa2 = headA;
            LinkNode pb2 = headB;
            while (pa != null) {
                pa = pa.next;
                pa2 = pa2.next;
            }
            while (pb != null) {
                pb = pb.next;
                pb2 = pb2.next;
            }

            // pa2, pb2 齐步走
            while (pa2 != null) {
                if (pa2 == pb2) {
                    return pa2;
                }
                pa2 = pa2.next;
                pb2 = pb2.next;
            }

            return null;
        }
    }

}
